数组中的逆序对

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

• 尝试了暴力方法只通过百分之50的用例，显然超时。
• 利用归并排序的比较方式，可以找到前面一个数大于后面一个数的逆序对。但是不能影响原数组，所以需要重新开一个数组用来存归并排序的结果。

function InversePairs(data)
{
    // write code here
    if(!data||data.length<2)return 0;
    const copy=data.slice();
    let count=0;
    count=MergeCount(data,copy,0,data.length-1);
    return count%1000000007;
}
function MergeCount(data,copy,start,end){
    if(start==end)return 0;
    const mid=end-start>>1;
    let left=MergeCount(copy,data,start,start+mid);
    let right=MergeCount(copy,data,start+mid+1,end);
    let [p,q,count, copyindex]=[start+mid,end,0,end];
    while(p>=start&&q>=start+mid+1){
        if(data[p]>data[q]){
            copy[copyindex--]=data[p--]
            count=count+q-start-mid;
        }
        else{
            copy[copyindex--]=data[q--];
        }
    }
    while(p>=start){
        copy[copyindex--]=data[p--]
    }
    while(q>=start+mid+1){
        copy[copyindex--]=data[q--]
    }
    return count+left+right;
}